/**
 * 面试题33：二叉搜索树的后序遍历序列
 */
public class Offer_33 {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return true;
        }
        return recur(postorder, 0, postorder.length - 1);
    }

    private boolean recur(int[] postorder, int start, int end) {
        // 终止条件： 当 start >= end，说明此子树节点数量 <= 1，无需判别正确性，因此直接返回 true
        if (start >= end) {
            return true;
        }
        int i = start;
        while (postorder[i] < postorder[end]) {
            i++;
        }
        // 下标为 j 的元素是第一个大于根节点的元素
        int j = i;
        while (postorder[i] > postorder[end]) {
            i++;
        }
        // 划分出左子树区间 [start, j-1]，右子树区间 [j, end-1]，根节点 end
        // i == end 判断此树是否正确
        // recur(postorder, start, j - 1) 判断此树的左子树是否正确
        // recur(postorder, j, end - 1) 判断此树的右子树是否正确
        return i == end && recur(postorder, start, j - 1) && recur(postorder, j, end - 1);
    }
}
